Pebble game

In mathematics and computer science, a pebble game is a type of mathematical game played by moving "pebbles" or "markers" on a directed graph. A variety of different pebble games exist.

Graph pebbling: A certain number of pebbles are distributed among the vertices of an undirected graph; the goal is to move at least one to a particular target vertex. But to move one pebble to an adjacent vertex, another pebble at the same vertex must be discarded.

A game known as "Black Pebbling" was developed in 1970; in it a pebble may be placed at any vertex of an acyclic digraph, provided that all its immediate ancestor vertices are also pebbled. (So an initial vertex with no ancestor can always be pebbled.) Pebbles may also be removed from the graph at will; the goal is to put a pebble on the target vertex while minimizing the number of pebbles in use at any time. Note that it is permitted to place a pebble on one vertex while simultaneously removing one from a parent vertex, effectively sliding the pebble. Hopcroft, Wolfgang J. Paul, and Valiant showed that the number of pebbles required never exceeds n/log n for n the number of vertices of the graph. This enabled them to prove that DTIME(f(n)) is contained in DSPACE(f(n)/log f(n)) for all time-constructible f.^[1]

A extension of "Black Pebbling", known as "Black-White Pebbling" was developed by Stephen Cook and Ravi Sethi in a 1976 paper.^[2] It also adds white pebbles, which may be placed at any vertex at will, but can only be removed if all the vertex's immediate descendant vertices are also pebbled. The goal remains to place a black pebble on the target vertex, but the pebbling of adjacent vertices may be done with pebbles of either color.

Takumi Kasai et al. developed a game in which a pebble may be moved along an edge-arrow to an unoccupied vertex only if a second pebble is located at a third, control vertex; the goal is to move a pebble to a target vertex. They determined the computational complexity of the one and two player versions of this game, and special cases thereof. In the two-player version, the players take turns moving pebbles. There may also be constraints on which pebbles a player can move.^[3]

References

^ John Hopcroft; Wolfgang J. Paul, Leslie Valiant (April 1977). "On time versus space". Journal of the ACM 24 (2): 332–337. doi:10.1145/322003.322015.
^ Stephen Cook; Ravi Sethi (1976). "Storage requirements for deterministic polynomial time recognizable languages". Journal of Computer and System Sciences 13 (1): 25–37. doi:10.1016/S0022-0000(76)80048-7.
^ Takumi Kasai; Akeo Adachi, Shigeki Iwata (1979). "Classes of pebble games and complete problems". SIAM Journal on Computing 8 (4): 574–586. doi:10.1137/0208046.